package com.demo.java.OD501_550.OD537;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【找出作弊的人(C卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146511538
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();  // 读取员工的数量
        List<Employee> all_employee = new ArrayList<>();  // 存放所有员工的信息
        List<int[]> pairs = new ArrayList<>();  // 存放符合条件的作弊员工对
        // 设置最小差值，初始为300，最大可能的分数差
        int min_val = 300;

        // 使用哈希表来记录每个分数对应的员工ID列表
        HashMap<Integer, List<Integer>> score_map = new HashMap<>();
        // 循环读取每个员工的ID和分数
        for (int i = 0; i < count; i++) {
            int a = in.nextInt();  // 员工的ID
            int b = in.nextInt();  // 员工的分数
            // 如果分数已存在，添加员工ID到该分数对应的列表中
            if (score_map.containsKey(b)) {
                List<Integer> temp = score_map.get(b);
                temp.add(a);  // 将员工ID加入列表
                score_map.put(b, temp);
            } else {
                // 如果分数不存在，则创建新的列表并加入员工ID
                List<Integer> temp = new ArrayList<>();
                temp.add(a);
                score_map.put(b, temp);
            }
            // 创建员工对象，并加入到员工列表中
            Employee employee = new Employee(a, b);
            all_employee.add(employee);
        }

        // 按照分数降序排列所有员工，分数高的排前面
        Collections.sort(all_employee);

        int i = 1;
        while (true) {
            if (i >= count) {
                // 当处理完所有员工后，按ID排序作弊员工对
                pairs.sort(Comparator.comparingInt(a -> a[0]));
                String output_str = "";
                // 将结果拼接成输出字符串
                for (int j = 0; j < pairs.size(); j++) {
                    output_str += pairs.get(j)[0] + " " + pairs.get(j)[1] + '\n';
                }
                // 输出所有符合条件的作弊员工对
                System.out.println(output_str.substring(0, output_str.length() - 1));
                break;
            } else {
                // 计算当前员工与前一个员工的分数差
                int temp = all_employee.get(i).score - all_employee.get(i - 1).score;
                // 如果当前的分数差小于之前的最小差值，则更新最小差值并清空现有的员工对
                if (min_val > temp) {
                    min_val = temp;
                    pairs = new ArrayList<>();
                    // 遍历前一个分数的所有员工ID，找到所有符合条件的员工对
                    for (int j = 0; j < score_map.get(all_employee.get(i - 1).score).size(); j++) {
                        // 如果前一个员工的ID小于当前员工的ID，则加入到作弊对中
                        if (score_map.get(all_employee.get(i - 1).score).get(j) < all_employee.get(i).id) {
                            pairs.add(new int[]{score_map.get(all_employee.get(i - 1).score).get(j), all_employee.get(i).id});
                        }
                    }
                }
                // 如果分数差等于最小差值，则继续查找符合条件的员工对
                else if (min_val == temp) {
                    // 遍历前一个分数的所有员工ID，找到所有符合条件的员工对
                    for (int j = 0; j < score_map.get(all_employee.get(i - 1).score).size(); j++) {
                        // 如果前一个员工的ID小于当前员工的ID，则加入到作弊对中
                        if (score_map.get(all_employee.get(i - 1).score).get(j) < all_employee.get(i).id) {
                            pairs.add(new int[]{score_map.get(all_employee.get(i - 1).score).get(j), all_employee.get(i).id});
                        }
                    }
                } else {
                    // 如果分数差大于最小差值，继续保持当前最小差值
                    min_val = min_val;
                }
            }
            i += 1;  // 继续处理下一个员工
        }
    }

    // 定义员工类
    public static class Employee implements Comparable<Employee> {
        int id;  // 员工ID
        int score;  // 员工分数

        // 构造函数
        public Employee(int id, int score) {
            this.id = id;
            this.score = score;
        }

        // 自定义排序：按照分数降序排列
        @Override
        public int compareTo(Employee o) {
            return -o.score + this.score;
        }
    }
}
